Optimal train dispatching by Benders-like reformulation

Train movements in railway lines are generally controlled by human dispatchers. As disruptions often occur, dispatchers take real-time scheduling and routing decisions in the attempt to minimize deviations from the ocial timetable. This optimization problem is called Train Dispatching. We represent it as a Mixed Integer Linear Programming model, and solve it by a Benders'-like decomposition within a suitable master/slave scheme. Interestingly, the master and the slave problems correspond to a macroscopic and microscopic representation of the railway, recently exploited in heuristic approaches to the problem. The decomposition, along with some new modeling ideas, allowed us to solve real-life instances of practical interest to optimality in short computing time. Automatic dispatching systems based on our macro/micro decomposition - in which both master and slave are solved heuristically - have been in operation in several Italian lines since year 2011. The exact approach described in this paper outperforms such systems on our test-bed of real-life instances. Furthermore, a system based on another version of the exact decomposition approach has been in operation since February 2014 on a line in Norway.